package algorthm.systemTraning.radixSort;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Arrays;
import java.util.Random;

/**
 * @className: RadixSort
 * @Description:
 * @Author: wangyifei
 * @Date: 2022/10/8 10:56
 */
public class RadixSort {
    private static Logger logger = LoggerFactory.getLogger(RadixSort.class);
    public static void sort(int[] array){
        int[] mid = new int[10];
        int[] help = new int[array.length];
        int max = 0 ;
        int tmp = 0 ;
        for(int e: array){
            if(max < ( tmp = hightest(e))){
                max = tmp ;
            }
        }
        for(int i = 1 ; i <= max ; i++){
            for(int e : array){
                mid[num(e,i)]++;
            }
            mid[1] = mid[1] + mid[0];
            for(int a = 2 ; a < mid.length ; a++){
                mid[a] = mid[a] + mid[a-1];
            }
            // 从左道右遍历，因为写入 help 的时候，也是从左道有插入的，这样就能能保持高位排序也是有序的
            // 例如，111 ， 123 ， 132
            // 当根据十位数拍好序是： 111 ， 123 ， 132
            // 然后，如果从左到右的顺序遍历 array , 则这几个数据插入后的顺序为 132,123,111
            // 所以给它来一个负负得正
            for(int a = array.length - 1 ; a >= 0 ; a--){
                help[--mid[num(array[a],i)]] = array[a] ;
            }
            for(int a = 0 ; a < help.length ; a++){
                array[a] = help[a];
            }
            for(int a = 0 ; a < mid.length ; a++){
                mid[a] = 0 ;
            }
        }
    }
    public static int hightest(int i){
        int ans = 0 ;
        while( (i = i/10) != 0){
            ans++;
        }
        return ans + 1;
    }

    public static int num(int i , int bit){
        if(bit <= 0){
            throw new RuntimeException("invalidate argument");
        }
        int a = 1 ;
        for(int e = 1 ; e < bit ; e++){
            a *= 10 ;
        }
        return (i/a)%10;
    }
    public static int[] randomArray(int range , int size){
        Random r = new Random();
        int randomSize = r.nextInt(size) + 1;
        int[] ans = new int[randomSize];
        for(int i = 0 ; i < randomSize ; i++){
            ans[i] = r.nextInt(range);
        }
        return ans ;
    }
    public static int[] copyOf(int[] array){
        int[] ans = new int[array.length];
        for(int i = 0 ; i < array.length ; i++){
            ans[i] = array[i];
        }
        return ans ;
    }
    public static void compare(int range , int size , int times){
        int[] array = null ;
        int[] array2 = null ;
        int[] arrayBak = null ;
        for(int i = 0 ; i < times ; i++){
            array = randomArray(range , size);
            array2 = copyOf(array);
            arrayBak = copyOf(array);
            sort(array);
            Arrays.sort(array2);
            for(int a = 0 ; a < array.length ; a++){
                if(array[a] != array2[a]){
                    System.out.println("Oops");
                }
            }
        }
    }

    public static void main(String[] args){
        compare(300 , 40 , 400000);
    }
}
